{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "## Открытый курс по машинному обучению. Сессия № 2\n",
    "</center>\n",
    "Автор материала: программист-исследователь Mail.ru Group, старший преподаватель Факультета Компьютерных Наук ВШЭ Юрий Кашницкий. Материал распространяется на условиях лицензии [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center>Занятие 7. Обучение без учителя\n",
    "## <center>Часть 3. Кластеризация. Метод k-средних (k-means)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Метод k-means – это один из наиболее популярных методов кластеризации. Основная идея метода заключается в том, что на каждой итерации пересчитывается центр масс (центроид) для каждого кластера, полученного на предыдущем шаге, затем объекты снова разбиваются на кластеры согласно тому, какой из новых центроидов находится ближе.\n",
    "\n",
    "Более формально, алгоритм принимает на вход выборку $X_1, \\dots, X_N$ и параметр $k$, указывающий необходимое число кластеров. Выходом алгоритма является набор из $k$ центроидов $\\{\\mu_1, \\dots, \\mu_k\\}$, с помощью которых кластеризация осуществляется путём отнесения каждого объекту к ближайшему центроиду. Все точки внутри одного кластера ближе к центроиду этого кластера, чем к центроиду любого другого кластера.\n",
    "\n",
    "Метод может быть сформулирован как задача оптимизации, а именно, минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров по центроидам и кластерам:\n",
    "$$\\sum_{i=1}^k \\sum_{X_n \\in C_i} ||X_n - \\mu_i||^2 \\rightarrow \\min, \\text{где $C_i$ - это $i$-ый кластер, $\\mu_i$ - это центр масс кластера $C_i$.}$$\n",
    "\n",
    "Решение такой задачи оптимизации является NP-трудной задачей, однако существует простой итеративный алгоритм, позволяющий найти локальный минимум указанного функционала. Алгоритм представляет собой последовательное чередование двух шагов до сходимости. \n",
    "\n",
    "Предположим, что как-то (например, случайно) выбраны начальные положения центроидов $\\mu_1, \\dots, \\mu_k$.\n",
    "\n",
    "1) *Этап кластеризациu.* На данном этапе происходит кластеризация выборки, как было описано выше: каждый объект относится к кластеру ближайшего к нему центроида. Формально, $$C_i = \\{X_n : ||X_n - \\mu_i|| \\leq ||X_n - \\mu_j||, \\text{ для всех $j \\in \\{1, \\dots, k\\}$}\\}.$$\n",
    "\n",
    "2) *Этап обновления центроидов.* На данном этапе центроиды пересчитываются, как центры масс только что построенных кластеров. Формально, $$\\mu_i = \\frac{1}{|C_i|}\\sum_{X_n \\in C_i} X_n.$$\n",
    "\n",
    "Этот процесс продолжается, пока центроиды и кластеризация продолжают изменяться. Алгоритм гарантированно сходится, однако не гарантируется достижение глобального минимума – а только одного из локальных минимумов. Другим недостатком алгоритма является то, что итоговая кластеризация зависит от выбора исходных центров кластеров. На практике алгоритм запускается несколько раз из различных начальных приближений, а полученные результаты некоторым образом усредняются. Стоит также отметить, что число кластеров необходимо знать заранее. Существуют различные эвристики, позволяющие выбирать в некотором смысле оптимальное число кластеров."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Пример: кластеризация игроков NBA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Про <a href=\"http://www.databasebasketball.com/about/aboutstats.htm\">признаки</a> игроков."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "nba = pd.read_csv(\"../../data/nba_2013.csv\")\n",
    "nba.head(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "from sklearn.decomposition import PCA\n",
    "\n",
    "kmeans = KMeans(n_clusters=5, random_state=1)\n",
    "numeric_cols = nba._get_numeric_data().dropna(axis=1)\n",
    "kmeans.fit(numeric_cols)\n",
    "\n",
    "\n",
    "# Visualizing using PCA\n",
    "pca = PCA(n_components=2)\n",
    "res = pca.fit_transform(numeric_cols)\n",
    "plt.figure(figsize=(12,8))\n",
    "plt.scatter(res[:,0], res[:,1], c=kmeans.labels_, s=50, cmap='viridis')\n",
    "plt.title('PCA')\n",
    "\n",
    "# Visualizing using 2 features: Total points vs. Total assists\n",
    "plt.figure(figsize=(12,8))\n",
    "plt.scatter(nba['pts'], nba['ast'], c=kmeans.labels_, s=50, cmap='viridis')\n",
    "plt.xlabel('Total points')\n",
    "plt.ylabel('Total assitances')\n",
    "\n",
    "# Visualizing using 2 features: Age vs. Minutes played\n",
    "plt.figure(figsize=(12,8))\n",
    "plt.scatter(nba['age'], nba['mp'], c=kmeans.labels_, s=50, cmap='viridis')\n",
    "plt.xlabel('Age')\n",
    "plt.ylabel('Minutes played');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Инициализация центроидов\n",
    "\n",
    "Метод `sklearn.KMeans` содержит параметры `n_init` (число запусков из различных начальных приближений) и `init`. Есть три способа инициализации центроидов:\n",
    "- `k-means++` – \"умная\" инициализация центроидов для ускорения сходимости.\n",
    "- `random` – случайная инициализация центроидов.\n",
    "- `ndarray` – заданная инициализация центроидов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Сжатие изображений с K-means"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.image as mpimg\n",
    "\n",
    "img = mpimg.imread('../../img/woman.jpg')[..., 1]\n",
    "plt.figure(figsize = (20, 12))\n",
    "plt.axis('off')\n",
    "plt.imshow(img, cmap='gray');"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.stats import randint\n",
    "from sklearn.cluster import MiniBatchKMeans\n",
    "\n",
    "X = img.reshape((-1, 1))\n",
    "k_means = MiniBatchKMeans(n_clusters=3)\n",
    "k_means.fit(X) \n",
    "values = k_means.cluster_centers_\n",
    "labels = k_means.labels_\n",
    "img_compressed = values[labels].reshape(img.shape)\n",
    "plt.figure(figsize = (20, 12))\n",
    "plt.axis('off')\n",
    "plt.imshow(img_compressed, cmap = 'gray');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Нахождение тем в текстах"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Применим KMeans для кластеризации текстов из 4 новостных категорий.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import time\n",
    "\n",
    "from sklearn import metrics\n",
    "from sklearn.datasets import fetch_20newsgroups\n",
    "from sklearn.feature_extraction.text import TfidfTransformer, TfidfVectorizer\n",
    "from sklearn.preprocessing import Normalizer\n",
    "\n",
    "categories = [\n",
    "    'alt.atheism',\n",
    "    'talk.religion.misc',\n",
    "    'comp.graphics',\n",
    "    'sci.space']\n",
    "\n",
    "print(\"Loading 20 newsgroups dataset for categories:\")\n",
    "print(categories)\n",
    "\n",
    "dataset = fetch_20newsgroups(subset='all', categories=categories,\n",
    "                             shuffle=True, random_state=42)\n",
    "\n",
    "print(\"%d documents\" % len(dataset.data))\n",
    "print(\"%d categories\" % len(dataset.target_names))\n",
    "\n",
    "labels = dataset.target\n",
    "true_k = np.unique(labels).shape[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Закодируем тексты с помощью TF-IDF признаков.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Extracting features from the training dataset using a sparse vectorizer\")\n",
    "vectorizer = TfidfVectorizer(max_df=0.5, max_features=1000,\n",
    "                             min_df=2, stop_words='english')\n",
    "\n",
    "X = vectorizer.fit_transform(dataset.data)\n",
    "print(\"n_samples: %d, n_features: %d\" % X.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**И применим к получившимся векторам метод $k$ средних.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "km = KMeans(n_clusters=true_k, init='k-means++', max_iter=100, n_init=1)\n",
    "\n",
    "print(\"Clustering sparse data with %s\" % km)\n",
    "t0 = time()\n",
    "km.fit(X)\n",
    "\n",
    "print(\"Homogeneity: %0.3f\" % metrics.homogeneity_score(labels, km.labels_))\n",
    "print(\"Completeness: %0.3f\" % metrics.completeness_score(labels, km.labels_))\n",
    "print(\"V-measure: %0.3f\" % metrics.v_measure_score(labels, km.labels_))\n",
    "print(\"Adjusted Rand-Index: %.3f\"\n",
    "      % metrics.adjusted_rand_score(labels, km.labels_))\n",
    "print(\"Silhouette Coefficient: %0.3f\"\n",
    "      % metrics.silhouette_score(X, km.labels_, sample_size=1000))\n",
    "\n",
    "order_centroids = km.cluster_centers_.argsort()[:, ::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Выведем слова, соответствующие самым весомым компонентам центров кластеров.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "terms = vectorizer.get_feature_names()\n",
    "for i in range(true_k):\n",
    "    print(\"Cluster %d:\" % (i + 1), end='')\n",
    "    for ind in order_centroids[i, :10]:\n",
    "        print(' %s' % terms[ind], end='')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Кластеризация рукописных цифр"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_digits\n",
    "\n",
    "digits = load_digits()\n",
    "\n",
    "X, y = digits.data, digits.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmeans = KMeans(n_clusters=10)\n",
    "kmeans.fit(X)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import adjusted_rand_score\n",
    "\n",
    "adjusted_rand_score(y, kmeans.predict(X))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "_, axes = plt.subplots(2, 5)\n",
    "for ax, center in zip(axes.ravel(), kmeans.cluster_centers_):\n",
    "    ax.matshow(center.reshape(8, 8), cmap=plt.cm.gray)\n",
    "    ax.set_xticks(())\n",
    "    ax.set_yticks(())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Полезные ссылки\n",
    "- <a href=\"https://en.wikipedia.org/wiki/K-means_clustering\">k-means</a> на Википедии\n",
    "- <a href=\"\">Статья</a> про нечеткую кластеризацию городов по социально-экономическим показателям на Хабрахабре"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "name": "lesson8_part1_kmeans.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
